Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/unix/volume22/nn6.4/part08

Internet Message Format | 1990-06-07 | 54.4 KB

Subject:  v22i043:  NN Newsreader, release 6.4, Part08/21
Newsgroups: comp.sources.unix
Approved: [e-mail]
X-Checksum-Snefru: 1aa4e288 878772b0 16cb5b7f fbf16c1f

Submitted-by: "Kim F. Storm" <[e-mail]>
Posting-number: Volume 22, Issue 43
Archive-name: nn6.4/part08

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# The tool that generated this appeared in the comp.sources.unix newsgroup;
# send mail to [e-mail] if you want that tool.
# Contents:  man/nnadmin.1m patchlevel.h regexp.c
# Wrapped by [e-mail] on Sun May  6 18:19:35 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 8 (of 22)."'
if test -f 'man/nnadmin.1m' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'man/nnadmin.1m'\"
else
  echo shar: Extracting \"'man/nnadmin.1m'\" \(20019 characters\)
  sed "s/^X//" >'man/nnadmin.1m' <<'END_OF_FILE'
X.TH NNADMIN 1M "Release 6.4"
X.\" (c) Copyright 1988, 1990, Kim F. Storm.  All rights reserved.
X.UC 4
X.SH NAME
Xnnadmin \- nn database administration
X.SH SYNOPSIS
X.B nnadmin
X[
X.I commands
X]
X.SH DESCRIPTION
X.I nnadmin
Xis a control program for the \fInnmaster\fP(1M) daemon which is
Xresponsible for building and maintaining the database used by the
X\fInn\fP(1) news reader.
X.LP
X\fInnadmin\fP allows you to display extracts from the log file,
Xdisplay the "raw" contents of the database, make consistency checks on
Xthe database, instruct the running \fInnmaster\fP to expire one or
Xmore groups, alter the options of the running \fInnmaster\fP, and much
Xmore.
X.LP
X\fInnadmin\fP runs in two modes: interactive and non-interactive.
X.LP
XIn interactive mode, simple one line menus are used to show the
Xavailable operations which are then selected by typing the letter
Xassociated with the command (normally the first letter in the command
Xname).
X.LP
XIn non-interactive mode, the
X.I commands
Xargument will be used as a series of key-strokes which are interpreted
Xexactly as if they were typed in from the keyboard in interactive
Xmode.  For example, to stop the \fInnmaster\fP, the following
Xinvokation of nnadmin can be used:
X.br
X    \fInnadmin\fP MK
X.br
Xwhich will select the (M)aster submenu from the main menu, and then
Xthe (K)ill entry from the submenu.
X.LP
XIn non-interactive mode, the menus are not displayed and the commands
Xare not echoed!  \fInnadmin\fP will exit when there are no more
Xkey-strokes to be read from the
X.I commands
Xargument.  It is not possible to specify a group name in the
X.I commands
Xargument, so the functionalities of \fInnadmin\fP that relates to
Xspecific groups are only available in interactive mode.
X.LP
XSome "dangerous" commands will require that you confirm them by
Xfollowing them by "Y" on the command line.  The most noteable are
XIY (initialize database) and EY (expire all groups).  These commands
Xwill be marked with a \fB[Y]\fP following the command name.
X.LP
XYou can also invoke an interactive \fInnadmin\fP using the
X.B :admin
Xcommand in \fInn\fP.
X.SH SHELL ESCAPES
XAt all prompts you can hit `!' to spawn a subshell.
X.LP
XThe working
Xdirectory of the subshell will be changed to the database directory
Xwhen invoked from the MASTER or DUMP menus, and it will changed to the
Xgroup's spool directory (if it exists) when invoked from the GROUP
Xmenu.
X.SH MAIN MENU
XFrom the main menu (identified by the
X.B ADMIN
Xprompt) you can select the following operations:
X.TP
X.B C)onf
X.br
XShow current configuration parameters such as directories, files,
Xprograms, network usage, etc.
X.TP
X\fBE)xpire [Y]\fP
X.br
XSend a request to the \fInnmaster\fP daemon to schedule (and run)
Xexpire for all groups in the database.
X.TP
X.B G)roups
X.br
XEnter the GROUP submenu.
X.TP
X\fBI)nit [Y]\fP
X.br
XSend a request to the \fInnmaster\fP daemon to recollect all
Xgroups in the database.
X.TP
X.B L)og
X.br
XEnter the LOG submenu.
X.TP
X.B M)aster
X.br
XEnter the MASTER submenu.
X.TP
X.B Q)uit
X.br
XQuit \fInnadmin\fP.
X.TP
X.B S)tat
X.br
XPrint general statistics about the database.  See the section on
XDatabase Statistics below.
X.TP
X.B U)pdate
X.br
XUpdate the incore copy of the database master index.
X.TP
X.B V)alidate
X.br
XMake a thorough consistency check on the database.  If inconsistencies
Xare found in a group, you will be asked whether a request should be
Xsent to the \fInnmaster\fP daemon to recollect the group (in
Xnon-interactive mode, requests will be sent automatically for all
Xcorrupted groups).
X.TP
X.B W)akeup
X.br
XSend a wakeup signal to the \fInnmaster\fP daemon to have it receive
Xmessages sent to it, perform the required actions, and then collect
Xarticles as necessary.
X.TP
X\fBZ\fP (silent validation)
X.br
XThis operation is identical to the Validate operation, expect that no
Xoutput is produced during the consistency check; this operation is
Xused by the \fInnmaster\fP to execute the \-\fBC\fP option.
X.SH THE MASTER MENU
XThe master menu (identified by the
X.B MASTER
Xprompt) provides access to overall database information, and to send
Xcontrol messages to the \fInnmaster\fP daemon.
X.TP
X.B D)ump
XEnter the DUMP submenu.
X.TP
X.B F)iles
X.br
XPrint a listing (using
X.IR ls (1))
Xof all the data and index files in the database.
X.TP
X.B G)roup
X.br
XPrint the master index entry for a single group identified by its
Xinternal group number.
X.TP
X.B K)ill
X.br
XStop the \fInnmaster\fP when it has finished its current task.
X.TP
X.B O)ptions
X.br
XChange the runtime options of the running \fInnmaster\fP daemon.
XCurrently, only the value of the \-r and \-e options can be modified.
X.TP
X.B S)tat
X.br
XPrint general statistics about the database.  See the section on
XDatabase Statistics below.
X.TP
X.B T)race
X.br
XTurn the trace option \-t on or off in the running \fInnmaster\fP.
X.SH THE DUMP MENU
XThe dump menu (identified by the
X.B DUMP
Xprompt) allows you to print the master index entry for various
Xselections of groups in the database.
X.TP
X.B A)ll
X.br
XPrint all groups in the database.
X.TP
X.B E)mpty
X.br
XPrint the empty groups in the database.
X.TP
X.B H)oles
XPrint the groups where the `min' field in the active file is not the
Xfirst article saved in the database (because it doesn't exist or
Xbecause it is ignored for some other reason, e.g. bad or old).
X.TP
X.B I)gnored
XPrint groups which are ignored, either in the GROUPS file or because
Xof some other condition (mainly no spool directory).
X.TP
X.B N)on-empty
X.br
XPrint the non-empty groups in the database.
X.TP
X.B V)alid
XPrint the groups which are present in the active file.
X.TP
X.B in(W)alid
XPrint the groups in the database which are not present in the active
Xfile.
X.SH THE LOG MENU
XThe log menu (identified by the
X.B LOG
Xprompt) enables you the extract specific entries from the log file,
Xand to truncate the log file.
X.LP
XThe entries in the log file share the following format:
X.sp 0.5v
X    <class>: <date> <time> (<user>): <message>
X.sp 0.5v
Xwhere <class> identifies the message class, the <date> and <time>
Xspecify when the entry was made, the <user> specifies who created the
Xentry (the letter "M" denote the \fInnmaster\fP), and the <message> is
Xthe text of the entry.
X.LP
XTo extract the log file entries of a specific class, simply enter the
Xletter identifying the class:
X.TP
X.B A - admin to master communication
X.br
XThis class of messages are related to the sending of messages from an
X\fInnadmin\fP program to the \fInnmaster\fP daemon.
X.TP
X.B B - bad articles
XReports about bad articles which have been ignored or removed
X(controlled by the \-\fBb\fP and \-\fBB\fP options to \fInnmaster\fP).
X.TP
X.B C - collection statistics
X.br
XStatistics about collection of new articles.  The message has the format:
X.br
X    Collect: \fInnn\fP art, \fIppp\fP gr, \fIttt\fP s
X.br
Xmeaning that
X.I nnn
Xarticles in
X.I ppp
Xgroups were collected in
X.I ttt
Xseconds (real time).
X.TP
X.B E - fatal errors
X.br
XFatal errors encountered during operation.  These errors require
Xmanual intervention to be fixed (some of the fatal errors occur if
Xthing that "cannot happen" happens anyway, and may indicate a bug
Xin the software).
X.TP
X.B M - nnmaster messages.
X.br
XMaster start/stop messages.
X.TP
X.B N - NNTP related messages
X.br
XVarious messages related to the NNTP part of the nnmaster, mostly
Xabout lost connections and failed attempts to connect to the NNTP
Xserver.  These messages should only appear if you use NNTP, and your
XNNTP server is down for some reason.
X.TP
X.B O - old articles
XReports related to ignoring (and removing) old articles when building
Xthe database (controlled by the \-\fBO\fP and \-\fBB\fP options to
X\fInnmaster\fP).
X.TP
X.B R - reports
X.br
XNon-fatal error which enables the \fInnmaster\fP to continue
Xoperation, but may prevent a user to run \fInn\fP (file access
Xproblems).  Reported problems should be checked.  The most common
Xreport message will probably be
X.br
X    some.group: no directory
X.br
Xwhich indicates that the spool directory for that group has
Xdisappeared (most likely because it has been rmgroup'ed).
X.TP
X.B T - trace output
X.br
XMessages produced as a result of using the \-t option on the
X\fInnmaster\fP.  This is primarily for debugging purposes.
X.TP
X.B U - usage statistics
X.br
XIf \fInn\fP is compiled with the STATISTICS option enabled, an entry
Xwill be made in the log file every time a user has spent more than
Xfive minutes on news reading.  The message will have the following format:
X.br
X    USAGE \fIhours.minutes\fP
X.br
XSince it is possible to
Xsuspend
X\fInn\fP, or leave the terminal while \fInn\fP is active, \fInn\fP
Xtries to be intelligent when it calculates the usage time so it will
Xreflect the actual time spent on news reading.  The usage statistics
Xcan be summarized using the \fInnusage\fP(1M) program.
X.TP
X.B V - validation errors
X.br
XWhen inconsistencies are detected in the database during validation,
Xan entry for each corrupted group will be entered in the log file.
X.TP
X.B X - expire statistics
X.br
XMessages similar to the Collect statistics reporting the result of
Xrunning expire on the database.  Reports related to ignoring, removing,
Xrenumbering, and reactivation of groups are also given class X.
X.LP
XTo extract a specific entry class,
X.IR grep (1)
Xis used, so it may take a while on a large log file.
X.LP
XThere are also a few special operations on the log file:
X.TP
X.B G)roup
X.br
XExtract the entries which refers to a specified group.
X.TP
X.B (1-9) tail
X.br
XInvoke
X.IR tail (1)
Xto extract the last 10-90 entries in the log file.
X.TP
X\fBspace\fP
X.br
XEquivalent to \fB1\fP (list last 10 lines of log).
X.TP
X.B (.) all
X.br
XDisplay the complete log file.
X.TP
X.B (@) clean [Y]
X.br
XMove the Log file to Log.old, and create a new empty Log file.  If you
Xwant to clean out the old log file as well, simply repeat the clean
Xoperation (this will result in an empty Log.old file.)
X.SH THE GROUP MENU
XWhen you enter the group menu (identified by the
X.B GROUP
Xprompt), \fInnadmin\fP will prompt you for the name of a news group,
Xwhich you can enter with the usual completion feature described in the
X\fInn\fP(1) manual.  You can then perform the following operations on
Xthe specified group:
X.TP
X.B C)lear_flag
X.br
XClear a group specific flag.  See the section on group flags below.
X.TP
X.B D)ata
X.br
XDump the contents of the data file containing the extracted article
Xheaders for the group.
X.TP
X.B E)xpire
X.br
XRequest the \fInnmaster\fP to run expire on the group.
X.TP
X.B F)iles
X.br
XList the files (using
X.IR ls (1))
Xcontaining the index and data for the group.
X.TP
X.B G)roup
X.br
XSwitch to another group.
X.TP
X.B H)eader
X.br
XDump the master index entry for the group.
X.TP
X.B R)ecollect
X.br
XRequest the \fInnmaster\fP to recollect all articles in the group.
X.TP
X.B S)et_flag
X.br
XSet a group specific flag.  See the section on group flags below.
X.TP
X.B V)alidate
X.br
XPerform validation on the group's database information.
X.TP
X.B Z)ap [Y]
X.br
XRemove group from news system - this will be done by running the
X\fIrmgroup\fP program which must reside in the NEWS_LIB directory.
XOf course, this should be done with great caution.
X.SH INDIVIDUAL GROUP FLAGS
XYou can set and clear the following flags for individual groups to
Xcontrol the future behaviour of \fInnmaster\fP on that group.
X.LP
XNotice that these flags will be reset to their default value if you
Xreinitialize the database using \fInnmaster\fP \-I.  To change these
Xflags permanently, they should be set or cleared in the GROUPS file.
X.TP
X.B A)lways_digest
X.br
XNormally, \fInnmaster\fP will only attempt to split digests into
Xindividual articles if it can easily recognize an article as a digest.
XThis requires that the word "digest" appears somewhere in the subject
Xline, and that one of the first few lines in the body of the article
Xloosely matches the subject.  A few news groups frequently receives
Xdigests which break one or both of these requirements.  To have
X\fInnmaster\fP split these digests into individual articles anyway,
Xyou can turn on the "always digest" flag on these news groups.
XThis will instruct \fInnmaster\fP to treat
X.I all
Xarticles in the group as digests (naturally, articles which are then
Xfound not to contain other articles are still treated as normal articles.)
X.TP
X.B C)ontrol
X.br
XThis is a special flag for the control group.  It indicates that the
X"Newsgroups:" field in the article header cannot be trusted (it does
Xnot specify the groups to which the article has been posted.)
X.TP
X.B D)irectory missing
X.br
XThis flag indicates that the spool directory for the news group cannot
Xbe found (the group has probably been removed with
X.IR rmgroup (1M)).
XIt is set automatically be the \fInnmaster\fP if it cannot
Xaccess the directory.  When the flag is set, \fInnmaster\fP completely
Xignores the group, so it can be used to disable news collection in
Xspecific groups.  If you recreate the group or the directory
Xmanually, you must also clear this flag to have the \fInnmaster\fP
Xrecognize the group again.
X.TP
X.B M)oderated
X.br
XIndicates that the group is moderated.  This flag is normally
Xinitialized automatically from the active file, and it should not be
Xchanged lightly.
X.TP
X.B N)ever_digest
X.br
XThis is the opposite of the "always digest" flag; when set, the
X\fInnmaster\fP will never attempt to split any articles in that group
Xinto subarticles.
X.SH DATABASE STATISTICS DISPLAY
XWhen you select the (S)tat operation in the main or master menus, you
Xwill get some general statistics about the database:
X.TP
Xinitialized
X.br
XThe time when the database was last rebuild using \fInnmaster\fP -I.
X.TP
Xlast_scan, last_size
X.br
XThe time stamp on the active file and its size the last time the
X\fInnmaster\fP read it.
X.TP
Xno of groups
X.br
XThe total number of groups in the database.
X.TP
XArticles
X.br
XThe total number of articles in all groups.  This is not an
Xexact number, because it will count split digests as a single article
X(making the number too small), and it may count some articles that
Xhave been expired (making the number too large).
X.TP
XDisk usage
X.br
XThe total number of (1 kbyte) disk blocks occupied by the database.
X.SH MASTER INDEX ENTRIES
XThe master index entries displayed when you select the (H)eader
Xoperation in the master and group menus contain the following information:
X.TP
X\fIgroup_name  group_number\fP
X.br
XThe first line of the display will show the name of the group and the
Xinternal group number which is used to identify the group in the database.
X.TP
Xfirst/last art
X.br
XThis is the numbers of the first and last article that are currently
Xstored in the database.
X.TP
Xactive info
X.br
XThis is the numbers of the first and last article in the news system
Xas read from the active file.  They will normally match the numbers
Xabove, but they may differ while the \fInnmaster\fP is working on the
Xgroup (or it has not yet collected all the articles in the group).
X.TP
XOffsets: index->..., data->...
X.br
XThese values show the starting position for the next write operation
Xon the index and data files.  They are primarily used for consistency
Xchecking and recovery after a system crash, but after an "expire by
Xrewrite" operation (expire method 2) which is performed "in-situ", the
Xdata and index files may physically be longer than the actual data
Xstored in them.
X.TP
XFlags:
X.br
XThis shows the current flags set for this group.  If no flags are set,
Xthe field is omitted from the display.  One extra flag which was not
Xexplained above is the BLOCKED flag; it is a temporary locking flag
Xset on a group by the \fInnmaster\fP while it is updating the database
Xfiles for that group to prevent \fInn\fP clients to access that group.
X.SH RAW DATABASE DISPLAY
XWhen you select the (D)ata operation on the group menu, you will get a
Xcombined display of the raw data and index files for that group.  The
Xindex file contains a single 32 bit value for each existing article
Xnumber.  This value is an offset into the data file pointing to the
Xheader for the corresponding article.
X.LP
XWhen \fInn\fP want to access the article from number N to the last
Xarticle, it looks up the offset for article number N in the index
Xfile, and uses this as the starting point for reading article header
Xinformation in the data file.  It then simply reads to the end of the
Xdata file in which the article headers for articles number N+1, N+2,
Xand so on follows immediately after the header for article number N.
X.LP
XThe article header information is presented in a very terse form; each
Xof the output lines are described below for reference purposes:
X.TP
Xoffset = \fIxxxx\fP    , article # = \fInnnnn\fP   (type)
X.br
XThis shows the offset into the data file and the article number.  The
Xoffset is stored in the index file for quick access.  If no \fItype\fP
Xis printed it is a normal article.  Other types are: "digest header"
Xand "digest sub-article".
X.TP
Xxpost(\fIcount\fP):  \fInnn\fP, \fInnn\fP, \fInnn\fP, ...
X.br
XCross-postings to other groups are encoded as a list of internal group
Xnumbers.
X.TP
Xts=\fInn\fP hp=\fInn\fP fp=\fInn\fP lp=\fInn\fP ref=\fInn\fP[+Re] lines=\fInn\fP
X.br
XThese values are used by \fInn\fP to sort, present, and access an
Xarticle:
X.br
X.B ts
Xis the
X.I time stamp
Xon the article; it is a simple encoding of the posting date and time
Xfound in the Date: field.
X.br
X.BR hp ,
X.BR fp ,
Xand
X.B lp
Xare offsets into the file containing the article text: the \fIheader
Xposition\fP, \fIfirst text position\fP, and \fIlast text position\fP.
XThe first will be zero for normal articles, but not for articles in a
Xsplit digest.  The last will be equal to the length of the file for
Xnormal articles, but not inside digests.
X.br
X.B ref
Xis the number of references on the Reference: line.  If "+Re" follows
Xthe number, the subject line contained a "Re:" prefix which has been
Xremoved.
X.TP
XSender(\fIlength\fP): \fIname\fP
X.br
XThe name of the sender in "ready to print" format, i.e. reduced to 16
Xcharacters as explained in the \fInn\fP manual.
X.TP
XSubj(\fIlength\fP): \fIsubject\fP
X.br
XThis is the full subject line from the article header (except for Re:
Xprefixes in various formats).
X.fi
X.SH FILES
XThe $db, $lib, and $news used below are synonyms for the DB_DIRECTORY,
XLIB_DIRECTORY, and the news system's lib directories respectively.
X.br
X.DT
X.ta \w'$db/DATA/\fInnn\fP.dx'u+3m
X.\"ta 0 16
X$db/MASTER    Database master index
X.br
X$db/GROUPS    News group names in MASTER file order
X.br
X$db/DATA/\fInnn\fP.x    Index file for group number \fInnn\fP
X.br
X$db/DATA/\fInnn\fP.d    Data file for group number \fInnn\fP
X.br
X$master/GATE    Message channel from \fInnadmin\fP to \fInnmaster\fP
X.br
X$master/MPID    The process id of the \fInnmaster\fP daemon.
X.br
X$Log    The log file (truncate it regularly!)
X.DT
X.LP
XThe MASTER file contains a record for each news group, occurring in
Xthe same sequence as the group names in the GROUPS file.  The sequence
Xalso defines the group numbers used to identify the files in the
Xdatabase and in a few other places.
X.LP
XThe GATE file will be created by \fInnadmin\fP when needed, and
Xremoved by \fInnmaster\fP when it has read it.  Therefore, to send a
Xmessage to the \fInnmaster\fP requires that you are allowed to write
Xin the $master directory.
X.SH SEE ALSO
Xnn(1), nncheck(1), nngrep(1), nntidy(1)
X.br
Xnnquery(1M), nnusage(1M), nnmaster(8)
X.SH WARNINGS
XThe GATE file is created with the owner and modes of the user that
Xruns \fInnadmin\fP which may cause problems if the owner of the
X\fInnmaster\fP process (normally "news") is not allowed to read the
Xcreated GATE file (a "umask" of 022 is ok.)  Unless you allow ordinary
Xusers to create files in the LIB directory where the GATE file
Xresides, only the owner of the directory (normally "news") and "root"
Xcan use \fInnadmin\fP to send messages to the \fInnmaster\fP.
XHowever, to send a wakeup signal to the master, anybody can run
X.br
X    \fInnmaster\fP -w
X.SH BUGS
XThe user interface is completely out of line with the rest of the
X\fInn\fP family, and the way to run \fInnadmin\fP in the
Xnon-interactive mode is a bit bizarre.  This is not likely to change,
Xbecause I believe there are more important things to do!
X.SH AUTHOR
XKim F. Storm, Texas Instruments A/S, Denmark
X.br
XE-mail: [e-mail]
END_OF_FILE
  if test 20019 -ne `wc -c <'man/nnadmin.1m'`; then
    echo shar: \"'man/nnadmin.1m'\" unpacked with wrong size!
  fi
  # end of 'man/nnadmin.1m'
fi
if test -f 'patchlevel.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'patchlevel.h'\"
else
  echo shar: Extracting \"'patchlevel.h'\" \(411 characters\)
  sed "s/^X//" >'patchlevel.h' <<'END_OF_FILE'
X/*
X *    (c) Copyright 1990, Kim Fabricius Storm.  All rights reserved.
X *
X *    Modification history:
X *
X *    1988-07-20: Release 6.0beta     (Denmark)
X *    1988-11-01: Release 6.1     (Europe)
X *    1989-03-21: Release 6.2beta    (FTP)
X *    1989-05-30: Release 6.3        (comp.sources.unix)
X *    1989-09-08: Release 6.3.7    (FTP)
X *    1990-03-03: Release 6.4beta    (FTP)
X *    1990-05-07: Release 6.4        (comp.sources.unix)
X */
X
X#define PATCHLEVEL 0
X
END_OF_FILE
  if test 411 -ne `wc -c <'patchlevel.h'`; then
    echo shar: \"'patchlevel.h'\" unpacked with wrong size!
  fi
  # end of 'patchlevel.h'
fi
if test -f 'regexp.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'regexp.c'\"
else
  echo shar: Extracting \"'regexp.c'\" \(30796 characters\)
  sed "s/^X//" >'regexp.c' <<'END_OF_FILE'
X/*
X * regexp.c - regular expression matching
X *
X * NOTICE: THIS CODE HAS BEEN MODIFIED TO FIT THE NN ENVIRONMENT.
X *
X * DESCRIPTION
X *
X *    This source was taken from the pax posting in comp.sources.unix.
X *
X *    Underneath the reformatting and comment blocks which were added to
X *    make it consistent with the rest of the code, you will find a
X *    modified version of Henry Specer's regular expression library.
X *    Henry's functions were modified to provide the minimal regular
X *    expression matching, as required by P1003.  Henry's code was
X *    copyrighted, and copy of the copyright message and restrictions
X *    are provided, verbatim, below:
X *
X *    Copyright (c) 1986 by University of Toronto.
X *    Written by Henry Spencer.  Not derived from licensed software.
X *
X *    Permission is granted to anyone to use this software for any
X *    purpose on any computer system, and to redistribute it freely,
X *    subject to the following restrictions:
X *
X *    1. The author is not responsible for the consequences of use of
X *         this software, no matter how awful, even if they arise
X *       from defects in it.
X *
X *    2. The origin of this software must not be misrepresented, either
X *       by explicit claim or by omission.
X *
X *    3. Altered versions must be plainly marked as such, and must not
X *       be misrepresented as being the original software.
X *
X *     Beware that some of this code is subtly aware of the way operator
X *     precedence is structured in regular expressions.  Serious changes in
X *     regular-expression syntax might require a total rethink.
X *
X * AUTHORS
X *
X *     Mark H. Colburn, NAPS International ([e-mail])
X *     Henry Spencer, University of Torronto ([e-mail])
X *
X * Sponsored by The USENIX Association for public distribution.
X *
X * $Log:    regexp.c,v $
X * Revision 1.1  88/12/23  18:02:32  mark
X * Initial revision
X *
X */
X
X#define NN
X
X/* Headers */
X
X#ifdef NN
X#include "config.h"
X#include "regexp.h"
X#else
X#include "pax.h"
X
X#ifndef lint
Xstatic char    *Ident = "$Id: regexp.c,v 1.1 88/12/23 18:02:32 mark Rel $";
X#endif
X#endif
X
X/*
X * The "internal use only" fields in regexp.h are present to pass info from
X * compile to execute that permits the execute phase to run lots faster on
X * simple cases.  They are:
X *
X * regstart    char that must begin a match; '\0' if none obvious
X * reganch    is the match anchored (at beginning-of-line only)?
X * regmust    string (pointer into program) that match must include, or NULL
X * regmlen    length of regmust string
X *
X * Regstart and reganch permit very fast decisions on suitable starting points
X * for a match, cutting down the work a lot.  Regmust permits fast rejection
X * of lines that cannot possibly match.  The regmust tests are costly enough
X * that regcomp() supplies a regmust only if the r.e. contains something
X * potentially expensive (at present, the only such thing detected is * or +
X * at the start of the r.e., which can involve a lot of backup).  Regmlen is
X * supplied because the test in regexec() needs it and regcomp() is computing
X * it anyway.
X */
X
X/*
X * Structure for regexp "program".  This is essentially a linear encoding
X * of a nondeterministic finite-state machine (aka syntax charts or
X * "railroad normal form" in parsing technology).  Each node is an opcode
X * plus a "nxt" pointer, possibly plus an operand.  "Nxt" pointers of
X * all nodes except BRANCH implement concatenation; a "nxt" pointer with
X * a BRANCH on both ends of it is connecting two alternatives.  (Here we
X * have one of the subtle syntax dependencies:  an individual BRANCH (as
X * opposed to a collection of them) is never concatenated with anything
X * because of operator precedence.)  The operand of some types of node is
X * a literal string; for others, it is a node leading into a sub-FSM.  In
X * particular, the operand of a BRANCH node is the first node of the branch.
X * (NB this is *not* a tree structure:  the tail of the branch connects
X * to the thing following the set of BRANCHes.)  The opcodes are:
X */
X
X/* definition    number    opnd?    meaning */
X#define    END    0        /* no    End of program. */
X#define    BOL    1        /* no    Match "" at beginning of line. */
X#define    EOL    2        /* no    Match "" at end of line. */
X#define    ANY    3        /* no    Match any one character. */
X#define    ANYOF    4        /* str    Match any character in this string. */
X#define    ANYBUT    5        /* str    Match any character not in this
X                 * string. */
X#define    BRANCH    6        /* node    Match this alternative, or the
X                 * nxt... */
X#define    BACK    7        /* no    Match "", "nxt" ptr points backward. */
X#define    EXACTLY    8        /* str    Match this string. */
X#define    NOTHING    9        /* no    Match empty string. */
X#define    STAR    10        /* node    Match this (simple) thing 0 or more
X                 * times. */
X#define    OPEN    20        /* no    Mark this point in input as start of
X                 * #n. */
X /* OPEN+1 is number 1, etc. */
X#define    CLOSE    30        /* no    Analogous to OPEN. */
X
X/*
X * Opcode notes:
X *
X * BRANCH    The set of branches constituting a single choice are hooked
X *        together with their "nxt" pointers, since precedence prevents
X *        anything being concatenated to any individual branch.  The
X *        "nxt" pointer of the last BRANCH in a choice points to the
X *        thing following the whole choice.  This is also where the
X *        final "nxt" pointer of each individual branch points; each
X *        branch starts with the operand node of a BRANCH node.
X *
X * BACK        Normal "nxt" pointers all implicitly point forward; BACK
X *        exists to make loop structures possible.
X *
X * STAR        complex '*', are implemented as circular BRANCH structures
X *        using BACK.  Simple cases (one character per match) are
X *        implemented with STAR for speed and to minimize recursive
X *        plunges.
X *
X * OPEN,CLOSE    ...are numbered at compile time.
X */
X
X/*
X * A node is one char of opcode followed by two chars of "nxt" pointer.
X * "Nxt" pointers are stored as two 8-bit pieces, high order first.  The
X * value is a positive offset from the opcode of the node containing it.
X * An operand, if any, simply follows the node.  (Note that much of the
X * code generation knows about this implicit relationship.)
X *
X * Using two bytes for the "nxt" pointer is vast overkill for most things,
X * but allows patterns to get big without disasters.
X */
X#define    OP(p)    (*(p))
X#define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
X#define    OPERAND(p)    ((p) + 3)
X
X/*
X * Utility definitions.
X */
X
X#define    FAIL(m)    { regerror(m); return(NULL); }
X#define    ISMULT(c)    ((c) == '*')
X#define    META    "^$.[()|*\\"
X#ifndef CHARBITS
X#define    UCHARAT(p)    ((int)*(unsigned char *)(p))
X#else
X#define    UCHARAT(p)    ((int)*(p)&CHARBITS)
X#endif
X
X/*
X * Flags to be passed up and down.
X */
X#define    HASWIDTH    01    /* Known never to match null string. */
X#define    SIMPLE        02    /* Simple enough to be STAR operand. */
X#define    SPSTART        04    /* Starts with * */
X#define    WORST        0    /* Worst case. */
X
X/*
X * Global work variables for regcomp().
X */
Xstatic char    *regparse;    /* Input-scan pointer. */
Xstatic int      regnpar;    /* () count. */
Xstatic char     regdummy;
Xstatic char    *regcode;    /* Code-emit pointer; ®dummy = don't. */
Xstatic long     regsize;    /* Code size. */
X
X/*
X * Forward declarations for regcomp()'s friends.
X */
X#ifndef STATIC
X#define    STATIC    static
X#endif
XSTATIC char    *reg();
XSTATIC char    *regbranch();
XSTATIC char    *regpiece();
XSTATIC char    *regatom();
XSTATIC char    *regnode();
XSTATIC char    *regnext();
XSTATIC void     regc();
XSTATIC void     reginsert();
XSTATIC void     regtail();
XSTATIC void     regoptail();
X#ifdef STRCSPN
XSTATIC int      strcspn();
X#endif
X
X/*
X - regcomp - compile a regular expression into internal code
X *
X * We can't allocate space until we know how big the compiled form will be,
X * but we can't compile it (and thus know how big it is) until we've got a
X * place to put the code.  So we cheat:  we compile it twice, once with code
X * generation turned off and size counting turned on, and once "for real".
X * This also means that we don't allocate space until we are sure that the
X * thing really will compile successfully, and we never have to move the
X * code and thus invalidate pointers into it.  (Note that it has to be in
X * one piece because free() must be able to free it all.)
X *
X * Beware that the optimization-preparation code in here knows about some
X * of the structure of the compiled regexp.
X */
Xregexp *regcomp(exp)
Xchar           *exp;
X{
X    register regexp *r;
X    register char  *scan;
X    register char  *longest;
X    register int    len;
X    int             flags;
X    extern char    *malloc();
X
X    if (exp == NULL)
X    FAIL("NULL argument");
X
X    /* First pass: determine size, legality. */
X    regparse = exp;
X    regnpar = 1;
X    regsize = 0L;
X    regcode = ®dummy;
X    regc(MAGIC);
X    if (reg(0, &flags) == NULL)
X    return (NULL);
X
X    /* Small enough for pointer-storage convention? */
X    if (regsize >= 32767L)    /* Probably could be 65535L. */
X    FAIL("regexp too big");
X
X    /* Allocate space. */
X    r = (regexp *) malloc(sizeof(regexp) + (unsigned) regsize);
X    if (r == NULL)
X    FAIL("out of space");
X
X    /* Second pass: emit code. */
X    regparse = exp;
X    regnpar = 1;
X    regcode = r->program;
X    regc(MAGIC);
X    if (reg(0, &flags) == NULL)
X    return (NULL);
X
X    /* Dig out information for optimizations. */
X    r->regstart = '\0';        /* Worst-case defaults. */
X    r->reganch = 0;
X    r->regmust = NULL;
X    r->regmlen = 0;
X    scan = r->program + 1;    /* First BRANCH. */
X    if (OP(regnext(scan)) == END) {    /* Only one top-level choice. */
X    scan = OPERAND(scan);
X
X    /* Starting-point info. */
X    if (OP(scan) == EXACTLY)
X        r->regstart = *OPERAND(scan);
X    else if (OP(scan) == BOL)
X        r->reganch++;
X
X    /*
X     * If there's something expensive in the r.e., find the longest
X     * literal string that must appear and make it the regmust.  Resolve
X     * ties in favor of later strings, since the regstart check works
X     * with the beginning of the r.e. and avoiding duplication
X     * strengthens checking.  Not a strong reason, but sufficient in the
X     * absence of others.
X     */
X    if (flags & SPSTART) {
X        longest = NULL;
X        len = 0;
X        for (; scan != NULL; scan = regnext(scan))
X        if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
X            longest = OPERAND(scan);
X            len = strlen(OPERAND(scan));
X        }
X        r->regmust = longest;
X        r->regmlen = len;
X    }
X    }
X    return (r);
X}
X
X/*
X - reg - regular expression, i.e. main body or parenthesized thing
X *
X * Caller must absorb opening parenthesis.
X *
X * Combining parenthesis handling with the base level of regular expression
X * is a trifle forced, but the need to tie the tails of the branches to what
X * follows makes it hard to avoid.
X */
Xstatic char *reg(paren, flagp)
Xint             paren;        /* Parenthesized? */
Xint            *flagp;
X{
X    register char  *ret;
X    register char  *br;
X    register char  *ender;
X    register int    parno;
X    int             flags;
X
X    *flagp = HASWIDTH;        /* Tentatively. */
X
X    /* Make an OPEN node, if parenthesized. */
X    if (paren) {
X    if (regnpar >= NSUBEXP)
X        FAIL("too many ()");
X    parno = regnpar;
X    regnpar++;
X    ret = regnode(OPEN + parno);
X    } else
X    ret = NULL;
X
X    /* Pick up the branches, linking them together. */
X    br = regbranch(&flags);
X    if (br == NULL)
X    return (NULL);
X    if (ret != NULL)
X    regtail(ret, br);    /* OPEN -> first. */
X    else
X    ret = br;
X    if (!(flags & HASWIDTH))
X    *flagp &= ~HASWIDTH;
X    *flagp |= flags & SPSTART;
X    while (*regparse == '|') {
X    regparse++;
X    br = regbranch(&flags);
X    if (br == NULL)
X        return (NULL);
X    regtail(ret, br);    /* BRANCH -> BRANCH. */
X    if (!(flags & HASWIDTH))
X        *flagp &= ~HASWIDTH;
X    *flagp |= flags & SPSTART;
X    }
X
X    /* Make a closing node, and hook it on the end. */
X    ender = regnode((paren) ? CLOSE + parno : END);
X    regtail(ret, ender);
X
X    /* Hook the tails of the branches to the closing node. */
X    for (br = ret; br != NULL; br = regnext(br))
X    regoptail(br, ender);
X
X    /* Check for proper termination. */
X    if (paren && *regparse++ != ')') {
X    FAIL("unmatched ()");
X    } else if (!paren && *regparse != '\0') {
X    if (*regparse == ')') {
X        FAIL("unmatched ()");
X    } else
X        FAIL("junk on end");/* "Can't happen". */
X    /* NOTREACHED */
X    }
X    return (ret);
X}
X
X/*
X - regbranch - one alternative of an | operator
X *
X * Implements the concatenation operator.
X */
Xstatic char  *regbranch(flagp)
Xint            *flagp;
X{
X    register char  *ret;
X    register char  *chain;
X    register char  *latest;
X    int             flags;
X
X    *flagp = WORST;        /* Tentatively. */
X
X    ret = regnode(BRANCH);
X    chain = NULL;
X    while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
X    latest = regpiece(&flags);
X    if (latest == NULL)
X        return (NULL);
X    *flagp |= flags & HASWIDTH;
X    if (chain == NULL)    /* First piece. */
X        *flagp |= flags & SPSTART;
X    else
X        regtail(chain, latest);
X    chain = latest;
X    }
X    if (chain == NULL)        /* Loop ran zero times. */
X    regnode(NOTHING);
X
X    return (ret);
X}
X
X/*
X - regpiece - something followed by possible [*]
X *
X * Note that the branching code sequence used for * is somewhat optimized:
X * they use the same NOTHING node as both the endmarker for their branch
X * list and the body of the last branch.  It might seem that this node could
X * be dispensed with entirely, but the endmarker role is not redundant.
X */
Xstatic char *regpiece(flagp)
Xint            *flagp;
X{
X    register char  *ret;
X    register char   op;
X    register char  *nxt;
X    int             flags;
X
X    ret = regatom(&flags);
X    if (ret == NULL)
X    return (NULL);
X
X    op = *regparse;
X    if (!ISMULT(op)) {
X    *flagp = flags;
X    return (ret);
X    }
X    if (!(flags & HASWIDTH))
X    FAIL("* operand could be empty");
X    *flagp = (WORST | SPSTART);
X
X    if (op == '*' && (flags & SIMPLE))
X    reginsert(STAR, ret);
X    else if (op == '*') {
X    /* Emit x* as (x&|), where & means "self". */
X    reginsert(BRANCH, ret);    /* Either x */
X    regoptail(ret, regnode(BACK));    /* and loop */
X    regoptail(ret, ret);    /* back */
X    regtail(ret, regnode(BRANCH));    /* or */
X    regtail(ret, regnode(NOTHING));    /* null. */
X    }
X    regparse++;
X    if (ISMULT(*regparse))
X    FAIL("nested *");
X
X    return (ret);
X}
X
X/*
X - regatom - the lowest level
X *
X * Optimization:  gobbles an entire sequence of ordinary characters so that
X * it can turn them into a single node, which is smaller to store and
X * faster to run.  Backslashed characters are exceptions, each becoming a
X * separate node; the code is simpler that way and it's not worth fixing.
X */
Xstatic char *regatom(flagp)
Xint            *flagp;
X{
X    register char  *ret;
X    int             flags;
X
X    *flagp = WORST;        /* Tentatively. */
X
X    switch (*regparse++) {
X    case '^':
X    ret = regnode(BOL);
X    break;
X    case '$':
X    ret = regnode(EOL);
X    break;
X    case '.':
X    ret = regnode(ANY);
X    *flagp |= HASWIDTH | SIMPLE;
X    break;
X    case '[':{
X        register int    class;
X        register int    classend;
X
X        if (*regparse == '^') {    /* Complement of range. */
X        ret = regnode(ANYBUT);
X        regparse++;
X        } else
X        ret = regnode(ANYOF);
X        if (*regparse == ']' || *regparse == '-')
X        regc(*regparse++);
X        while (*regparse != '\0' && *regparse != ']') {
X        if (*regparse == '-') {
X            regparse++;
X            if (*regparse == ']' || *regparse == '\0')
X            regc('-');
X            else {
X            class = UCHARAT(regparse - 2) + 1;
X            classend = UCHARAT(regparse);
X            if (class > classend + 1)
X                FAIL("invalid [] range");
X            for (; class <= classend; class++)
X                regc(class);
X            regparse++;
X            }
X        } else
X            regc(*regparse++);
X        }
X        regc('\0');
X        if (*regparse != ']')
X        FAIL("unmatched []");
X        regparse++;
X        *flagp |= HASWIDTH | SIMPLE;
X    }
X    break;
X    case '(':
X    ret = reg(1, &flags);
X    if (ret == NULL)
X        return (NULL);
X    *flagp |= flags & (HASWIDTH | SPSTART);
X    break;
X    case '\0':
X    case '|':
X    case ')':
X    FAIL("internal urp");    /* Supposed to be caught earlier. */
X    break;
X    case '*':
X    FAIL("* follows nothing");
X    break;
X    case '\\':
X    if (*regparse == '\0')
X        FAIL("trailing \\");
X    ret = regnode(EXACTLY);
X    regc(*regparse++);
X    regc('\0');
X    *flagp |= HASWIDTH | SIMPLE;
X    break;
X    default:{
X        register int    len;
X        register char   ender;
X
X        regparse--;
X        len = strcspn(regparse, META);
X        if (len <= 0)
X        FAIL("internal disaster");
X        ender = *(regparse + len);
X        if (len > 1 && ISMULT(ender))
X        len--;        /* Back off clear of * operand. */
X        *flagp |= HASWIDTH;
X        if (len == 1)
X        *flagp |= SIMPLE;
X        ret = regnode(EXACTLY);
X        while (len > 0) {
X        regc(*regparse++);
X        len--;
X        }
X        regc('\0');
X    }
X    break;
X    }
X
X    return (ret);
X}
X
X/*
X - regnode - emit a node
X */
Xstatic char *regnode(op)
Xchar            op;
X{
X    register char  *ret;
X    register char  *ptr;
X
X    ret = regcode;
X    if (ret == ®dummy) {
X    regsize += 3;
X    return (ret);
X    }
X    ptr = ret;
X    *ptr++ = op;
X    *ptr++ = '\0';        /* Null "nxt" pointer. */
X    *ptr++ = '\0';
X    regcode = ptr;
X
X    return (ret);
X}
X
X/*
X - regc - emit (if appropriate) a byte of code
X */
Xstatic void regc(b)
Xchar            b;
X{
X    if (regcode != ®dummy)
X    *regcode++ = b;
X    else
X    regsize++;
X}
X
X/*
X - reginsert - insert an operator in front of already-emitted operand
X *
X * Means relocating the operand.
X */
Xstatic void reginsert(op, opnd)
Xchar            op;
Xchar           *opnd;
X{
X    register char  *src;
X    register char  *dst;
X    register char  *place;
X
X    if (regcode == ®dummy) {
X    regsize += 3;
X    return;
X    }
X    src = regcode;
X    regcode += 3;
X    dst = regcode;
X    while (src > opnd)
X    *--dst = *--src;
X
X    place = opnd;        /* Op node, where operand used to be. */
X    *place++ = op;
X    *place++ = '\0';
X    *place++ = '\0';
X}
X
X/*
X - regtail - set the next-pointer at the end of a node chain
X */
Xstatic void regtail(p, val)
Xchar           *p;
Xchar           *val;
X{
X    register char  *scan;
X    register char  *temp;
X    register int    offset;
X
X    if (p == ®dummy)
X    return;
X
X    /* Find last node. */
X    scan = p;
X    for (;;) {
X    temp = regnext(scan);
X    if (temp == NULL)
X        break;
X    scan = temp;
X    }
X
X    if (OP(scan) == BACK)
X    offset = scan - val;
X    else
X    offset = val - scan;
X    *(scan + 1) = (offset >> 8) & 0377;
X    *(scan + 2) = offset & 0377;
X}
X
X/*
X - regoptail - regtail on operand of first argument; nop if operandless
X */
Xstatic void regoptail(p, val)
Xchar           *p;
Xchar           *val;
X{
X    /* "Operandless" and "op != BRANCH" are synonymous in practice. */
X    if (p == NULL || p == ®dummy || OP(p) != BRANCH)
X    return;
X    regtail(OPERAND(p), val);
X}
X
X/*
X * regexec and friends
X */
X
X/*
X * Global work variables for regexec().
X */
Xstatic char    *reginput;    /* String-input pointer. */
Xstatic char    *regbol;        /* Beginning of input, for ^ check. */
Xstatic char   **regstartp;    /* Pointer to startp array. */
Xstatic char   **regendp;    /* Ditto for endp. */
X
X/*
X * Forwards.
X */
XSTATIC int      regtry();
XSTATIC int      regmatch();
XSTATIC int      regrepeat();
X
X#ifdef DEBUG
Xint             regnarrate = 0;
Xvoid            regdump();
XSTATIC char    *regprop();
X#endif
X
X/*
X - regexec - match a regexp against a string
X */
Xint regexec(prog, string)
Xregister regexp *prog;
Xregister char  *string;
X{
X    register char  *s;
X
X    /* Be paranoid... */
X    if (prog == NULL || string == NULL) {
X    regerror("NULL parameter");
X    return (0);
X    }
X    /* Check validity of program. */
X    if (UCHARAT(prog->program) != MAGIC) {
X    regerror("corrupted program");
X    return (0);
X    }
X    /* If there is a "must appear" string, look for it. */
X    if (prog->regmust != NULL) {
X    s = string;
X    while ((s = strchr(s, prog->regmust[0])) != NULL) {
X        if (strncmp(s, prog->regmust, prog->regmlen) == 0)
X        break;        /* Found it. */
X        s++;
X    }
X    if (s == NULL)        /* Not present. */
X        return (0);
X    }
X    /* Mark beginning of line for ^ . */
X    regbol = string;
X
X    /* Simplest case:  anchored match need be tried only once. */
X    if (prog->reganch)
X    return (regtry(prog, string));
X
X    /* Messy cases:  unanchored match. */
X    s = string;
X    if (prog->regstart != '\0')
X    /* We know what char it must start with. */
X    while ((s = strchr(s, prog->regstart)) != NULL) {
X        if (regtry(prog, s))
X        return (1);
X        s++;
X    }
X    else
X    /* We don't -- general case. */
X    do {
X        if (regtry(prog, s))
X        return (1);
X    } while (*s++ != '\0');
X
X    /* Failure. */
X    return (0);
X}
X
X/*
X - regtry - try match at specific point
X */
X#ifdef __STDC__
X
Xstatic int regtry(regexp *prog, char *string)
X
X#else
X
Xstatic int regtry(prog, string)
Xregexp         *prog;
Xchar           *string;
X
X#endif
X{
X    register int    i;
X    register char **sp;
X    register char **ep;
X
X    reginput = string;
X    regstartp = prog->startp;
X    regendp = prog->endp;
X
X    sp = prog->startp;
X    ep = prog->endp;
X    for (i = NSUBEXP; i > 0; i--) {
X    *sp++ = NULL;
X    *ep++ = NULL;
X    }
X    if (regmatch(prog->program + 1)) {
X    prog->startp[0] = string;
X    prog->endp[0] = reginput;
X    return (1);
X    } else
X    return (0);
X}
X
X/*
X - regmatch - main matching routine
X *
X * Conceptually the strategy is simple:  check to see whether the current
X * node matches, call self recursively to see whether the rest matches,
X * and then act accordingly.  In practice we make some effort to avoid
X * recursion, in particular by going through "ordinary" nodes (that don't
X * need to know whether the rest of the match failed) by a loop instead of
X * by recursion.
X */
X#ifdef __STDC__
X
Xstatic int regmatch(char *prog)
X
X#else
X
Xstatic int regmatch(prog)
Xchar           *prog;
X
X#endif
X{
X    register char  *scan;    /* Current node. */
X    char           *nxt;    /* nxt node. */
X
X    scan = prog;
X#ifdef DEBUG
X    if (scan != NULL && regnarrate)
X    fprintf(stderr, "%s(\n", regprop(scan));
X#endif
X    while (scan != NULL) {
X#ifdef DEBUG
X    if (regnarrate)
X        fprintf(stderr, "%s...\n", regprop(scan));
X#endif
X    nxt = regnext(scan);
X
X    switch (OP(scan)) {
X    case BOL:
X        if (reginput != regbol)
X        return (0);
X        break;
X    case EOL:
X        if (*reginput != '\0')
X        return (0);
X        break;
X    case ANY:
X        if (*reginput == '\0')
X        return (0);
X        reginput++;
X        break;
X    case EXACTLY:{
X        register int    len;
X        register char  *opnd;
X
X        opnd = OPERAND(scan);
X        /* Inline the first character, for speed. */
X        if (*opnd != *reginput)
X            return (0);
X        len = strlen(opnd);
X        if (len > 1 && strncmp(opnd, reginput, len) != 0)
X            return (0);
X        reginput += len;
X        }
X        break;
X    case ANYOF:
X        if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
X        return (0);
X        reginput++;
X        break;
X    case ANYBUT:
X        if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
X        return (0);
X        reginput++;
X        break;
X    case NOTHING:
X        break;
X    case BACK:
X        break;
X    case OPEN + 1:
X    case OPEN + 2:
X    case OPEN + 3:
X    case OPEN + 4:
X    case OPEN + 5:
X    case OPEN + 6:
X    case OPEN + 7:
X    case OPEN + 8:
X    case OPEN + 9:{
X        register int    no;
X        register char  *save;
X
X        no = OP(scan) - OPEN;
X        save = reginput;
X
X        if (regmatch(nxt)) {
X            /*
X             * Don't set startp if some later invocation of the same
X             * parentheses already has.
X             */
X            if (regstartp[no] == NULL)
X            regstartp[no] = save;
X            return (1);
X        } else
X            return (0);
X        }
X        break;
X    case CLOSE + 1:
X    case CLOSE + 2:
X    case CLOSE + 3:
X    case CLOSE + 4:
X    case CLOSE + 5:
X    case CLOSE + 6:
X    case CLOSE + 7:
X    case CLOSE + 8:
X    case CLOSE + 9:{
X        register int    no;
X        register char  *save;
X
X        no = OP(scan) - CLOSE;
X        save = reginput;
X
X        if (regmatch(nxt)) {
X            /*
X             * Don't set endp if some later invocation of the same
X             * parentheses already has.
X             */
X            if (regendp[no] == NULL)
X            regendp[no] = save;
X            return (1);
X        } else
X            return (0);
X        }
X        break;
X    case BRANCH:{
X        register char  *save;
X
X        if (OP(nxt) != BRANCH)    /* No choice. */
X            nxt = OPERAND(scan);    /* Avoid recursion. */
X        else {
X            do {
X            save = reginput;
X            if (regmatch(OPERAND(scan)))
X                return (1);
X            reginput = save;
X            scan = regnext(scan);
X            } while (scan != NULL && OP(scan) == BRANCH);
X            return (0);
X            /* NOTREACHED */
X        }
X        }
X        break;
X    case STAR:{
X        register char   nextch;
X        register int    no;
X        register char  *save;
X        register int    min;
X
X        /*
X         * Lookahead to avoid useless match attempts when we know
X         * what character comes next.
X         */
X        nextch = '\0';
X        if (OP(nxt) == EXACTLY)
X            nextch = *OPERAND(nxt);
X        min = (OP(scan) == STAR) ? 0 : 1;
X        save = reginput;
X        no = regrepeat(OPERAND(scan));
X        while (no >= min) {
X            /* If it could work, try it. */
X            if (nextch == '\0' || *reginput == nextch)
X            if (regmatch(nxt))
X                return (1);
X            /* Couldn't or didn't -- back up. */
X            no--;
X            reginput = save + no;
X        }
X        return (0);
X        }
X        break;
X    case END:
X        return (1);        /* Success! */
X        break;
X    default:
X        regerror("memory corruption");
X        return (0);
X        break;
X    }
X
X    scan = nxt;
X    }
X
X    /*
X     * We get here only if there's trouble -- normally "case END" is the
X     * terminating point.
X     */
X    regerror("corrupted pointers");
X    return (0);
X}
X
X/*
X - regrepeat - repeatedly match something simple, report how many
X */
X#ifdef __STDC__
X
Xstatic int regrepeat(char *p)
X
X#else
X
Xstatic int regrepeat(p)
Xchar           *p;
X
X#endif
X{
X    register int    count = 0;
X    register char  *scan;
X    register char  *opnd;
X
X    scan = reginput;
X    opnd = OPERAND(p);
X    switch (OP(p)) {
X    case ANY:
X    count = strlen(scan);
X    scan += count;
X    break;
X    case EXACTLY:
X    while (*opnd == *scan) {
X        count++;
X        scan++;
X    }
X    break;
X    case ANYOF:
X    while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
X        count++;
X        scan++;
X    }
X    break;
X    case ANYBUT:
X    while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
X        count++;
X        scan++;
X    }
X    break;
X    default:            /* Oh dear.  Called inappropriately. */
X    regerror("internal foulup");
X    count = 0;        /* Best compromise. */
X    break;
X    }
X    reginput = scan;
X
X    return (count);
X}
X
X
X/*
X - regnext - dig the "nxt" pointer out of a node
X */
X#ifdef __STDC__
X
Xstatic char *regnext(register char *p)
X
X#else
X
Xstatic char *regnext(p)
Xregister char  *p;
X
X#endif
X{
X    register int    offset;
X
X    if (p == ®dummy)
X    return (NULL);
X
X    offset = NEXT(p);
X    if (offset == 0)
X    return (NULL);
X
X    if (OP(p) == BACK)
X    return (p - offset);
X    else
X    return (p + offset);
X}
X
X#ifdef DEBUG
X
XSTATIC char    *regprop();
X
X/*
X - regdump - dump a regexp onto stdout in vaguely comprehensible form
X */
X#ifdef __STDC__
X
Xvoid regdump(regexp *r)
X
X#else
X
Xvoid regdump(r)
Xregexp         *r;
X
X#endif
X{
X    register char  *s;
X    register char   op = EXACTLY;    /* Arbitrary non-END op. */
X    register char  *nxt;
X    extern char    *strchr();
X
X
X    s = r->program + 1;
X    while (op != END) {        /* While that wasn't END last time... */
X    op = OP(s);
X    printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
X    nxt = regnext(s);
X    if (nxt == NULL)    /* nxt ptr. */
X        printf("(0)");
X    else
X        printf("(%d)", (s - r->program) + (nxt - s));
X    s += 3;
X    if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
X        /* Literal string, where present. */
X        while (*s != '\0') {
X        putchar(*s);
X        s++;
X        }
X        s++;
X    }
X    putchar('\n');
X    }
X
X    /* Header fields of interest. */
X    if (r->regstart != '\0')
X    printf("start `%c' ", r->regstart);
X    if (r->reganch)
X    printf("anchored ");
X    if (r->regmust != NULL)
X    printf("must have \"%s\"", r->regmust);
X    printf("\n");
X}
X
X/*
X - regprop - printable representation of opcode
X */
X#ifdef __STDC__
X
Xstatic char *regprop(char *op)
X
X#else
X
Xstatic char *regprop(op)
Xchar           *op;
X
X#endif
X{
X    register char  *p;
X    static char     buf[50];
X
X    strcpy(buf, ":");
X
X    switch (OP(op)) {
X    case BOL:
X    p = "BOL";
X    break;
X    case EOL:
X    p = "EOL";
X    break;
X    case ANY:
X    p = "ANY";
X    break;
X    case ANYOF:
X    p = "ANYOF";
X    break;
X    case ANYBUT:
X    p = "ANYBUT";
X    break;
X    case BRANCH:
X    p = "BRANCH";
X    break;
X    case EXACTLY:
X    p = "EXACTLY";
X    break;
X    case NOTHING:
X    p = "NOTHING";
X    break;
X    case BACK:
X    p = "BACK";
X    break;
X    case END:
X    p = "END";
X    break;
X    case OPEN + 1:
X    case OPEN + 2:
X    case OPEN + 3:
X    case OPEN + 4:
X    case OPEN + 5:
X    case OPEN + 6:
X    case OPEN + 7:
X    case OPEN + 8:
X    case OPEN + 9:
X    sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
X    p = NULL;
X    break;
X    case CLOSE + 1:
X    case CLOSE + 2:
X    case CLOSE + 3:
X    case CLOSE + 4:
X    case CLOSE + 5:
X    case CLOSE + 6:
X    case CLOSE + 7:
X    case CLOSE + 8:
X    case CLOSE + 9:
X    sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
X    p = NULL;
X    break;
X    case STAR:
X    p = "STAR";
X    break;
X    default:
X    regerror("corrupted opcode");
X    break;
X    }
X    if (p != NULL)
X    strcat(buf, p);
X    return (buf);
X}
X#endif
X
X/*
X * The following is provided for those people who do not have strcspn() in
X * their C libraries.  They should get off their butts and do something
X * about it; at least one public-domain implementation of those (highly
X * useful) string routines has been published on Usenet.
X */
X#ifdef STRCSPN
X/*
X * strcspn - find length of initial segment of s1 consisting entirely
X * of characters not from s2
X */
X
X#ifdef __STDC__
X
Xstatic int strcspn(char *s1, char *s2)
X
X#else
X
Xstatic int strcspn(s1, s2)
Xchar           *s1;
Xchar           *s2;
X
X#endif
X{
X    register char  *scan1;
X    register char  *scan2;
X    register int    count;
X
X    count = 0;
X    for (scan1 = s1; *scan1 != '\0'; scan1++) {
X    for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
X        if (*scan1 == *scan2++)
X        return (count);
X    count++;
X    }
X    return (count);
X}
X#endif
X
X
X/*
X - regsub - perform substitutions after a regexp match
X */
X#ifdef __STDC__
X
Xvoid regsub(regexp *prog, char *source, char *dest)
X
X#else
X
Xvoid regsub(prog, source, dest)
Xregexp         *prog;
Xchar           *source;
Xchar           *dest;
X
X#endif
X{
X    register char  *src;
X    register char  *dst;
X    register char   c;
X    register int    no;
X    register int    len;
X    extern char    *strncpy();
X
X    if (prog == NULL || source == NULL || dest == NULL) {
X    regerror("NULL parm to regsub");
X    return;
X    }
X    if (UCHARAT(prog->program) != MAGIC) {
X    regerror("damaged regexp fed to regsub");
X    return;
X    }
X    src = source;
X    dst = dest;
X    while ((c = *src++) != '\0') {
X    if (c == '&')
X        no = 0;
X    else if (c == '\\' && '0' <= *src && *src <= '9')
X        no = *src++ - '0';
X    else
X        no = -1;
X
X    if (no < 0) {        /* Ordinary character. */
X        if (c == '\\' && (*src == '\\' || *src == '&'))
X        c = *src++;
X        *dst++ = c;
X    } else if (prog->startp[no] != NULL && prog->endp[no] != NULL) {
X        len = prog->endp[no] - prog->startp[no];
X        strncpy(dst, prog->startp[no], len);
X        dst += len;
X        if (len != 0 && *(dst - 1) == '\0') {    /* strncpy hit NUL. */
X        regerror("damaged match string");
X        return;
X        }
X    }
X    }
X    *dst++ = '\0';
X}
X
X
X#ifdef __STDC__
X
Xvoid regerror(char *s)
X
X#else
X
Xvoid regerror(s)
Xchar           *s;
X
X#endif
X{
X#ifdef NN
X    msg("REGEXP ERROR: %s", s);
X#else
X    fprintf(stderr, "regexp(3): %s", s);
X    exit(1);
X#endif
X}
END_OF_FILE
  if test 30796 -ne `wc -c <'regexp.c'`; then
    echo shar: \"'regexp.c'\" unpacked with wrong size!
  fi
  # end of 'regexp.c'
fi
echo shar: End of archive 8 \(of 22\).
cp /dev/null ark8isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 22 archives.
    rm -f ark[1-9]isdone ark[1-9][0-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0

exit 0 # Just in case...